/*7
 * 
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package sapxepmang;
import java.util.Scanner;
public class mysort {
    int a[],b[];
  /* void chep()
    {
        for(int i=1;i<a.length;i++)
            a[i]=b[i];
    }*/

void in()
{
    for(int i=1;i<a.length;i++)
        System.out.print(a[i]   +"  ");
}
void qs(int l, int r)
    {
        int x= a[(l+r)/2];
        int i=l, j=r;
        while(i<j)
        {
            while(a[i]<x) i++;
            while(a[j]>x) j--;
            if(i<=j)
            {
                int t=a[i]; a[i]=a[j]; a[j]=t; i++; j--;
            }
        }
        if(i<r) qs(i,r);
        if(l<j) qs(l,j);
    }

    void Quick_Sort()
    {
        qs(1, a.length-1);
    }

    
/*void sapxep(){
        for(int i=2;i<a.length;i++)
        {
            int v=a[i];
            int k=i-1;
            while(k>0&&a[k]>v)
            {
                a[k+1]=a[k];
                k--;
            }
            a[k+1]=v;
        }
}*/
/* void merge(int low, int mid, int high)
   {
      int []b = new int[high-low+2];
      int h,i,j,k;
       h=low;
      i=0;
      j=mid+1;
      while((h<=mid)&&(j<=high)) {
          if(a[h]<=a[j])  b[++i]=a[h++];
          else  b[++i]=a[j++];
      }
      if(h>mid)
        for(k=j;k<=high;k++)  b[++i]=a[k];
      else
        for(k=h;k<=mid;k++)   b[++i]=a[k];
      for(k=1;k<=high-low+1;k++)   a[k+low-1]=b[k];
   }

   void Merge_Sort(int low, int high) {
      if(low<high){
        int mid=(low+high)/2;
        Merge_Sort(low,mid);
        Merge_Sort( mid+1,high);
        merge(low,mid,high);
      }
   }
   void Merge_Sort(){
      Merge_Sort(1, a.length-1);
   }
/* void SelectSort(){
        for(int i=1;i<a.length;i++){
            int vtm=i; //gan vi tri min = i
            for(int j=i+1;j<a.length;j++){
                if(a[j]<a[vtm]) vtm=j;
            }
            if(i!=vtm){
                int t=a[i];
                a[i]=a[vtm];
                a[vtm]=t;
            }
        }
    }
/*void merge(int l,int r)
{
    int []t=new int[r-l+2];
    int k=0,m=(l+r)/2;
    int i=l,j=m+1;
    while(i<=m&&j<=r)
    {
        if(a[i]<a[j]) c[++k]=a[i++];
        else c[++k]=a[j++];
    }
    if(i<=m)while(i<=m)
}
/*void heap(int start,int end)
{
    int j=start;
    while(j<=end/2)
    {
        
        int maxchild=2*j;
        if(2*j<end && a[maxchild]<a[maxchild+1])
            maxchild=maxchild +1;
                if(a[j]<a[maxchild])
                {
                    int t=a[j];
                    a[j]=a[maxchild];
                    a[maxchild]=t;
                    j=maxchild;
                }
         else break;
             
    }
}
void heapsort()
{
    int k=a.length-1;
    for(int i=k/2;i>0;i--)
        heap(i,k);
    for(int i=k;i>=1;i--)
    {
        int t=a[i];
        a[i]=a[1];
        a[1]=t;
        heap(1,i-1);
        
    }
}*/
 public static void main(String[] args) {
        mysort x=new mysort();
       x.sinh();
       x.in();
      // x.Merge_Sort();
      // x.SelectSort();
       //x.heapsort();
       x.Quick_Sort();
         System.out.print("\n");
         x.in();
       
 }
}
    /*    double t1,t2;
        t1=System.currentTimeMillis();
        //x.sinh();
       //x.in();
       x.sapxep();
        x.heapsort();
         System.out.print("\n");
        x.in();


        t2=System.currentTimeMillis();
       // System.out.print("\n thoi gian can sap xep= + (t2-t1)");
     //   x.chep();
       
       */
        // x.heapsort();
         
 